package cn.dapeng.interview;

import java.util.Random;
import java.util.Stack;

/**
 * 一个栈中所有元素都是整数，现在想将栈中元素从顶到底按从大到小顺序排序，只允许申请一个栈
 * 除此之外，可以申请新的变量，但不能申请别的数据结构
 */
public class Stack_Order_T01 {

    public static Stack sorted(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<>();
        while (!stack.isEmpty()) {
            Integer item = stack.pop();

            if (help.isEmpty()) {
                help.push(item);
            } else {
                if (item >= help.peek()) {
                    help.push(item);
                } else {
                    while (!help.isEmpty()) {
                        stack.push(help.pop());
                    }
                    help.push(item);
                }
            }
        }
        return help;
    }

    public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<>();

        while (!stack.isEmpty()) {
            Integer cur = stack.pop();
            while (!help.isEmpty() && cur > help.peek()) {
                stack.push(help.pop());
            }
            help.push(cur);
        }

        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        Random r = new Random();
        for (int i = 0; i < 10; i++) {
            stack.push(r.nextInt(100));
        }

        //stack = sorted(stack);
        sortStackByStack(stack);
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }

    }
}
